package com.wenhao.interview.pinduoduo;


import java.util.Scanner;

/**
 * @author Wenhao Tong
 * @create 2021-07-25 19:46
 */
public class Main3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int i = 0;i < T;i++) {
            long A = scanner.nextLong();
            long B = scanner.nextLong();
            long C = scanner.nextLong();
            long Q = scanner.nextLong();
            if (isInA(A,B,C,Q)){
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }
    public static boolean isInA (long A,long B,long C,long Q) {
        if (A == Q) {
            return true;
        }
        boolean flag1 = false;
        boolean flag2 = false;
        if (Q % C == 0 && C != 1) {
            flag1 = isInA(A,B, C,Q / C);
        }
        if (Q > B + A) {
            flag2 = isInA(A,B,C,Q - B);
        }
        return flag1 || flag2;
    }
}
